package com.yulongtian.oneProblemEveryDay.month202302;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/remove-sub-folders-from-the-filesystem/
 * 可
 *
 * @author yulongTian
 * @create 2023-02-08 15:51
 */
public class Test06 {
    public static void main(String[] args) {
        String[] folder = {"/a", "/a/b/c", "/a/b/d"};
        System.out.println(removeSubfolders(folder));
    }

    /**
     * 按字典顺序对文件夹进行排序。
     * 在数组中插入当前元素，然后循环，直到我们删除所有的子文件夹，重复这个过程，直到没有元素留下。
     * 可  5.33%+99.41%
     *
     * @param folder
     * @return
     */
    public static List<String> removeSubfolders(String[] folder) {
        List<String> ans = new ArrayList<>();
        Arrays.sort(folder);
        for (int i = 0; i < folder.length; i++) {
            if (folder[i].equals("#")) {
                continue;
            }
            int len1 = folder[i].length();
            for (int j = i + 1; j < folder.length; j++) {
                if (folder[j].startsWith(folder[i])) {
                    //是前缀
                    if (folder[j].length() == len1) {
                        folder[j] = "#";
                        continue;
                    }
                    if (folder[j].charAt(len1) == '/') {
                        folder[j] = "#";
                    }
                }
            }
            ans.add(folder[i]);
        }
        return ans;
    }

}
